// https://leetcode-cn.com/problems/word-search/
// 79. 单词搜索
// 给定一个 mxn 二维字符网格 board 和一个字符串单词 word。如果 word 存
// 在于网格，返回 true；否则，返回 false
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是哪些
// 水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
function exist(board: string[][], word: string): boolean {
    const rows = board.length;
    const columns = board[0].length;
    const wl = word.length;
    const visited: boolean[][] = new Array(rows)
        .fill(0)
        .map(() => new Array(columns).fill(false));
    const directions = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1],
    ];

    function check(i: number, j: number, idx: number): boolean {
        if (board[i][j] !== word[idx]) return false;
        if (idx === wl - 1) return true;

        visited[i][j] = true;
        let result = false;
        for (const [dx, dy] of directions) {
            const ii = i + dy;
            const jj = j + dx;
            if (
                ii >= 0 &&
                ii < rows &&
                jj >= 0 &&
                jj < columns &&
                !visited[ii][jj] &&
                check(ii, jj, idx + 1)
            ) {
                result = true;
                break;
            }
        }
        visited[i][j] = false;

        return result;
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < columns; j++) {
            const flag = check(i, j, 0);
            if (flag) return true;
        }
    }

    return false;
}
